Tail recursion (rekurencja ogonowa)

Tail recursion (pol. rekurencja ogonowa) jest szczególnym przypadkiem rekurencji, w którym wywołanie funkcji rekurencyjnej występuje jako ostatnia operacja w ciele funkcji. Dzięki temu kompilator lub interpreter może zastosować optymalizację zwaną eliminacją wywołań ogonowych (ang. tail‑call optimization, TCO), przekształcając rekurencję w iterację i unikając dodatkowego zużycia stos.

Definicja

Funkcja f jest rekurencją ogonową, jeśli każde wywołanie f wewnątrz jej definicji znajduje się w pozycji ostatniej (tzw. tail position) i nie jest otoczone żadną dodatkową operacją, taką jak dodawanie, mnożenie, czy wywołanie innej funkcji po powrocie z wywołania rekurencyjnego.

Zasada działania

1. Podczas wywołania rekurencyjnego interpreter sprawdza, czy wywołanie znajduje się w pozycji ogonowej.
2. Jeżeli tak, zamiast tworzyć nową ramkę stosu, aktualna ramka jest nadpisywana danymi potrzebnymi do kolejnego wywołania.
3. Proces ten powtarza się, aż warunek zakończenia zostanie spełniony, a funkcja zakończy się bez dodatkowego „złapania” zwracanej wartości.

W praktyce oznacza to, że algorytmy rekurencyjne, które można zapisać w formie rekurencji ogonowej, działają w czasie liniowym i zużywają stałą ilość pamięci stosu (O(1) pamięci dodatkowej).

Tail-call elimination (eliminacja wywołań ogonowych)

Eliminacja wywołań ogonowych jest techniką implementacyjną stosowaną w kompilatorach i interpreterach. Systemy, które ją wspierają, mogą przetworzyć funkcję rekurencyjną ogonowo‑rekurencyjną tak, jakby była ona pętlą while lub for. Przykłady języków, które posiadają wbudowaną obsługę TCO:

• Scheme – wymóg języka.
• Haskell – optymalizacja wykonywana przez kompilator GHC.
• Erlang – kluczowy element modelu aktorów.
• Lisp (np. Common Lisp, Clojure) – wsparcie opcjonalne.
• OCaml – eliminuje wywołania ogonowe przy kompilacji.

Przykłady

1. Prosta suma w Scheme

(define (sum tail acc)
  (if (null? tail)
      acc
      (sum (cdr tail) (+ (car tail) acc))))

Wywołanie sum jest ostatnią operacją w każdej gałęzi, więc interpreter może zastosować TCO.

2. Silnia w C (z TCO)

unsigned long factorial_tail(unsigned long n, unsigned long acc) {
    if (n == 0) return acc;
    return factorial_tail(n - 1, n * acc);
}

/* funkcja pomocnicza */
unsigned long factorial(unsigned long n) {
    return factorial_tail(n, 1);
}

Standardowy kompilator GCC z flagą -O2 może zamienić tę rekurencję na iterację.

3. Rekurencja ogonowa w Pythonie (bez wbudowanej TCO)

def sum_tail(lst, acc=0):
    if not lst:
        return acc
    return sum_tail(lst[1:], acc + lst[0])

Python nie wykonuje eliminacji wywołań ogonowych, dlatego taki kod może prowadzić do przepełnienia stosu przy dużych listach, mimo że jest formalnie ogonowy.

Porównanie z tradycyjną rekurencją

Cecha	Rekurencja tradycyjna	Rekurencja ogonowa
Zużycie stosu	Wzrost proporcjonalny do głębokości rekurencji (O(n))	Stałe (O(1)) przy TCO
Wymagania językowe	Nie wymaga specjalnego wsparcia	Wymaga wsparcia kompilatora/interpretatora
Czytelność	Może być bardziej intuicyjna przy podziałach problemu	Często wymaga dodatkowego akumulatora
Możliwość optymalizacji	Rzadko	Wysoka (eliminacja wywołań)

Zastosowania

• Algorytmy przetwarzające listy lub drzewa (np. traversale, sumowanie, mapowanie).
• Implementacja automatów skończonych i parserów w stylu rekurencyjnego zstępu (recursive descent).
• Programowanie funkcyjne – wiele funkcji w językach funkcjonalnych jest zaprojektowanych jako tail‑recursive, aby umożliwić nieograniczoną głębokość wywołań.
• Systemy czasu rzeczywistego (np. w Erlangu) – eliminacja stosu zmniejsza ryzyko awarii.

Wady i ograniczenia

Choć tail recursion może znacznie ograniczyć zużycie pamięci, istnieją pewne ograniczenia:

• Nie wszystkie języki wspierają eliminację wywołań ogonowych (np. Python, Java – wymagają ręcznej optymalizacji).
• Przepisanie algorytmu na wersję ogonową może wymagać wprowadzenia dodatkowych parametrów (akumulatorów), co utrudnia czytelność.
• W niektórych przypadkach optymalizacja może być wyłączona przez kompilator ze względu na debugowanie lub włączone flagi bezpieczeństwa.

Historia i kontekst

Pierwsze prace nad optymalizacją wywołań ogonowych pojawiły się w latach 1970 w kontekście języka LISP. W 1978 roku pojawił się raport Scheme, w którym TCO stało się wymogiem językowym. Od tego czasu koncepcja została zaadaptowana w wielu językach funkcyjnych i niektórych imperatywnych.

Bibliografia

Artykuły i pozycje, które rozwijają temat rekurencji ogonowej:

• John C. Reynolds – Definitional Interpreters for Higher‑Order Programming Languages (1972).
• Guy L. Steele Jr. – Tail‑Call Optimization in Scheme (1977).
• Alfred V. Aho, Jeffrey D. Ullman – Principles of Compiler Design (1977) – rozdział o optymalizacji kolejnych wywołań.

Patrz także: rekurencja, programowanie funkcyjne, analiza algorytmiczna, język programowania.